package cn.datastruct.five;

import java.util.Arrays;

/**
 * 思路：
 * 1.求出最后一个非叶子节点length / 2 - 1
 * 2.得出这个节点以及下面叶子节点之间的最大值，把当前节点的值赋给最大值的位置
 * 3.依次遍历从leng / 2 - 1到零，这样一个最大堆就是构建完成了
 * 4.从最后一个开始遍历，最大值一个在堆顶，将堆顶元素和最后一个元素交换，再进行一次调整
 */
public class HeapSort {
    public static void main(String[] args) {
        int[] arr = {12, 9, 13, 14, 7, 8, 11};
        headSort(arr);
    }

    public static void heapSort(int[] arr) {
        System.out.println("堆排序");
        int temp = 0;
//        adjustHeap(arr, 2, arr.length);
//        System.out.println("第一次堆排序：" + Arrays.toString(arr));
//        adjustHeap(arr, 1, arr.length);
//        System.out.println("第二次堆排序：" + Arrays.toString(arr));
//        adjustHeap(arr, 0, arr.length);
//        System.out.println("第三次堆排序：" + Arrays.toString(arr));
//        temp = arr[arr.length - 1];
//        arr[arr.length - 1] = arr[0];
//        arr[0] = temp;
//        adjustHeap(arr, 0, arr.length - 1);
//        System.out.println("第四次堆排序：" + Arrays.toString(arr));
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            adjustHeap(arr, i, arr.length);//让最大的一个元素调大最面
        }

        for (int i = arr.length - 1; i > 0; i--) {//让最大的一个元素放到最末尾，
            temp = arr[i];
            arr[i] = arr[0];
            arr[0] = temp;
            adjustHeap(arr, 0, i);//让最大的元素放在上面
        }
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 举例 {4 ,6, 8, 5, 9} ->{4 ,9, 8, 5, 6}->{9 ,6, 8, 5, 4}->{4 ,5, 8, 6, 9}
     *
     * @param arr    表示待排序的数组
     * @param i      元素的位置
     * @param length 初始的数组长度减去排好序的元素的个数
     */
    public static void adjustHeap(int[] arr, int i, int length) {//小顶堆
        int temp = arr[i];//保留当前节点的值
        for (int j = i * 2 + 1; j < length; j = 2 * j + 1) {//指向下一个叶子节点
            if (j + 1 < length && arr[j + 1] < arr[j]) {
                j++;
            }
            if (arr[j] < temp) {//交换两个值
                arr[i] = arr[j];
                i = j;
            } else {
                break;
            }
            arr[i] = temp;//这一步？

        }
    }
//    public static void adjustHeap(int[] arr, int i, int length) {//大顶堆
//        int temp = arr[i];//保存当前元素的值
//        for (int j = i * 2 + 1; j < length; j = 2 * j + 1) {//转向左子树节点，length为最大长度，j = 2 * j + 1
//            if (j + 1 < length && arr[j] < arr[j + 1]) {
//                j++;//如果右子树节点大于左子树节点就交换
//            }
//            if (arr[j] >= temp) {
//                arr[i] = arr[j];//交换位置
//                i = j;//让i指向末尾位置
//            } else {
//                break;//如果最大叶子节点比temp小则下一个
//            }
//        }
//        arr[i] = temp;//for循环结束后将temp填入
//    }

    public static void headSort(int[] arr) {
        //得到数组的长度
        int length = arr.length;
        //得到一个大顶堆
        for (int i = length / 2 - 1; i >= 0; i--) {//从下往上传递
            adustheap(i, arr, length);
        }

        //将最大值和相对最后一个元素交换
        for (int i = length - 1; i > 0 ; i--) {
            int temp = arr[0];//最大值
            arr[0] = arr[i];
            arr[i] = temp;
            //调整大顶堆
            adustheap(0,arr, i);
        }
        System.out.println(Arrays.toString(arr));
    }

    public static void adustheap(int i, int[] arr,int length) {
        //保存当前节点的值
        int temp = arr[i];
        for (int j = i * 2 + 1; j < length; j = 2 * j + 1) {//从当前节点的左节点开始
            if (j + 1 < length && arr[j] < arr[j + 1]) {//如果当前节点的左节点小于右节点，则j++, j + 1 防止越界
                j++;
            }
            if (arr[j] > temp) {
                arr[i] = arr[j];
                i = j;
                arr[i] = temp;
            } else {
                break;
            }
        }
    }
}
